package com.c2b.algorithm.leetcode.base;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * <a href='https://leetcode.cn/problems/equal-row-and-column-pairs/'>相等行列对(Equal Row and Column Pairs)</a>
 * <p>给你一个下标从 0 开始、大小为 n x n 的整数矩阵 grid ，返回满足 Ri 行和 Cj 列相等的行列对 (Ri, Cj) 的数目。</p>
 * <p>如果行和列以相同的顺序包含相同的元素（即相等的数组），则认为二者是相等的。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：grid = [
 *              [3,2,1],
 *              [1,7,6],
 *              [2,7,7]
 *          ]
 *      输出：1
 *      解释：存在一对相等行列对：
 *          - (第 2 行，第 1 列)：[2,7,7]
 *
 * 示例 2：
 *      输入：grid = [[3,1,2,2],[1,4,4,5],[2,4,2,2],[2,4,2,2]]
 *      输出：3
 *      解释：存在三对相等行列对：
 *          - (第 0 行，第 0 列)：[3,1,2,2]
 *          - (第 2 行, 第 2 列)：[2,4,2,2]
 *          - (第 3 行, 第 2 列)：[2,4,2,2]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>n == grid.length == grid[i].length</li>
 *     <li>1 <= n <= 200</li>
 *     <li>1 <= grid[i][j] <= 10^5</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/10 16:43
 */
public class LC2356EqualRowAndColumnPairs_M {

    static class Solution {
        public int equalPairs(int[][] grid) {
            int n = grid.length;
            Map<String, Integer> map = new HashMap<>();
            StringBuilder key ;
            for (int i = 0; i < n; i++) {
                key = new StringBuilder();
                for (int j = 0; j < n; j++) {
                    key.append(grid[i][j]).append("-");
                }

                map.put(key.toString(), map.getOrDefault(key.toString(), 0) + 1);
            }
            int res = 0;
            for (int i = 0; i < n; i++) {
                key = new StringBuilder();
                for (int j = 0; j < n; j++) {
                    key.append(grid[j][i]).append("-");
                }
                res += map.getOrDefault(key.toString(),0);
            }
            return res;
        }


        public int equalPairs2(int[][] grid) {
            int n = grid.length;
            int[][] copy = new int[n][n];
            // 转动矩阵，让第i行成为第i列
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    copy[j][i] = grid[i][j];
                }
            }
            int res = 0;
            // 行
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    res += Arrays.equals(grid[i], copy[j]) ? 1 : 0;
                }
            }
            return res;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] ints1 = {
                {3, 2, 1},
                {1, 7, 6},
                {2, 7, 7}
        };
        System.out.println(solution.equalPairs(ints1));
        int[][] ints2 = {
                {3, 1, 2, 2},
                {1, 4, 4, 5},
                {2, 4, 2, 2},
                {2, 4, 2, 2}
        };
        System.out.println(solution.equalPairs(ints2));
    }
}

